package main

import (
	"fmt"
	"time"
)

func main() {

	//arr := sorting.Init(50000, 1000)
	arr := []int{0, 5,8,7,13,88,99,40}
	now := time.Now().UnixNano() / 1e6
	Sort(arr)
	unix := time.Now().UnixNano() / 1e6

	fmt.Println(unix - now)

	fmt.Print(arr)

}

func Sort(a []int) {
	n := len(a)-1
	k := n
	buildHeap(a, n)
	for k > 1 {

		a[1], a[k] = a[k], a[1]
		heapify(a, k-1, 1)
		k--
	}

}

func buildHeap(a [] int, n int) {
	for i := n / 2; i >= 1; i-- {
		heapify(a, n, i)
	}
}
func heapify(a [] int, n, i int) {

	for {
		maxPos := i
		if i*2 <= n && a[i] < a[i*2] {
			maxPos = i * 2
		}
		if i*2+1 <= n && a[maxPos] < a[i*2+1] {
			maxPos = i*2 + 1
		}

		if maxPos == i {

			break
		}
		a[i], a[maxPos] = a[maxPos], a[i]
		i = maxPos
	}
}
